package leetcode.d_300_plus;

// 零钱兑换II
// https://leetcode.cn/problems/coin-change-ii/
public class P518 {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        for (int i=0; i<=n; i++) {
            dp[i][0] = 1;
        }

        for (int j=1; j<=amount; j++) {
            for (int i=1; i<=n; i++) {
                if (coins[i-1] <= j) {
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][amount];
    }


    // 可以采用回溯（DFS）的方法
    int res;
    public int change2(int amount, int[] coins) {
        res = 0;
        backtrack(amount, coins, 0, 0);
        return res;
    }

    public void backtrack(int amount, int[] coins, int idx, int sum) {
        if (idx == coins.length) {
            if (sum == amount) {
                res++;
            }
            return;
        }
        if (sum == amount) {
            res++;
            return;
        }
        if (sum > amount) {
            return;
        }
        // 不选当前硬币值
        backtrack(amount, coins, idx+1, sum);
        // 选当前硬币值
        backtrack(amount, coins, idx, sum+coins[idx]);
    }

    public static void main(String[] args) {
        int amount = 5;
        int[] coins = {1,2,5};
        P518 solution = new P518();
        System.out.println(solution.change(amount, coins)); // 4
    }
}
